// qsort.cpp
#include <iostream>
#include <string>

using namespace std;

// general definition of ordering R(t1,t2)
// returns >0 if t2 R t1, <=0 otherwise
template <class T>
void partition(T *array,int n,int (*R)(T,T),int &p)
{
 // partition around the first element of the array
 // any element could have been used.

 // p is the index of the element around which the
 // partition is made
 // pe (declared below) points to the element after
 // the second partition
 int i = n-1, pe = 1;
 T temp1,temp2;

 p=0;
 while(i > 0)
 {
  if(R(array[p],array[pe]) > 0)
  {
   temp1 = array[p]; temp2 = array[p+1];
   array[p++] = array[pe];// put element in first partition
   array[p] = temp1;      // move element around which partition
                          // is made, one element right
   if(pe-p > 0)           // if the second partition is not empty
   array[pe] = temp2;     // move second partition one element right
  }
  pe++;
  i--;
 }
}

template <class T>
void qsort(T *array,int n,int (*R)(T,T))
{
 int pelement;
 if(n <= 1) return;

 partition(array,n,R,pelement);
 qsort(array,pelement,R);
 qsort(array+pelement+1,n-pelement-1,R);
}

int less_int(int n1,int n2) { return n1>n2; }
int less_string(string n1,string n2) { return (n1>n2); }

int main(void)
{
 int test1[9] = {1,5,3,7,2,9,4,6,8};
 string test2[6] = {"orange","grape","apple","pear","banana","peach"};
 int i;

 qsort<int>(test1,9,less_int);
 qsort<string>(test2,6,less_string);
 for(i=0;i<9;i++) cout << test1[i] << "  ";
 cout << endl;
 for(i=0;i<6;i++) cout << test2[i] << "  ";
 cout << endl;
}


